package com.ctrip.study.algorithm.tree;

import org.junit.Test;

import junit.framework.TestCase;

public class Tree extends TestCase {

	private Node root;

	public Node find(int data) {
		Node current = root;
		while (current.getData() != data) {
			if (data < current.getData()) {
				current = current.getLeftNode();
			} else {
				current = current.getRightNode();
			}
			if (current == null) {
				return null;
			}
		}
		return current;
	}

	public void insert(int data) {
		Node insertNode = new Node(data);
		if (root == null) {
			root = insertNode;
			return;
		} else {
			Node current = root;
			Node parent = null;
			while (true) {
				parent = current;
				if (data < current.getData()) { // go left
					current = current.getLeftNode();
					if (current == null) {
						parent.setLeftNode(insertNode);
						return;
					}
				} else {
					current = current.getRightNode();
					if (current == null) {
						parent.setRightNode(insertNode);
						return;
					}
				}
			}
		}
	}

	public void treeLDR() {
		Node current = root;
		inOrder(current);
	}

	private void inOrder(Node node) {
		if (node == null) {
			return;
		}
		inOrder(node.getLeftNode());
		System.out.println(node.getData());
		inOrder(node.getRightNode());
	}

	public Node findMin() {
		Node current = root;
		while (current.getLeftNode() != null) {
			current = current.getLeftNode();
		}
		return current;
	}

	public Node findMax() {
		Node current = root;
		while (current.getRightNode() != null) {
			current = current.getRightNode();
		}
		return current;
	}

	public void delete(int data) {
		Node current = root;
		Node parent = null;
		boolean isLeftNode = true;
		while (current.getData() != data) {
			parent = current;
			if (data < current.getData()) {
				current = current.getLeftNode();
				isLeftNode = true;
			} else {
				current = current.getRightNode();
				isLeftNode = false;
			}
			if (current == null) {
				System.out.println("未找到要删除的节点");
				return;
			}
		}
		// 删除节点的左右子树都为空，则直接删除
		if (current.getLeftNode() == null && current.getRightNode() == null) {
			if (current == root) {
				root = null;
			}
			if (isLeftNode) {
				parent.setLeftNode(null);
			} else {
				parent.setRightNode(null);
			}
		}
		// 删除节点的有一个子节点
		if (current.getLeftNode() == null) {
			if (current == root) {
				root = current.getRightNode();
			} else if (isLeftNode) {
				parent.setLeftNode(current.getRightNode());
			} else {
				parent.setRightNode(current.getRightNode());
			}
		}
		if(current.getRightNode() == null){
			if(current == root){
				root = current.getLeftNode();
			} else if (isLeftNode){
				parent.setLeftNode(current.getLeftNode());
			} else {
				parent.setRightNode(current.getLeftNode());
			}
		}
		else{
			Node successor = findSuccessor(current);  
            if(current == root){  
                root = successor;  
            }else if(isLeftNode){  
                parent.setLeftNode(successor);  
            }else{  
                parent.setRightNode(successor);  
            }  
            successor.setLeftNode(current.getLeftNode());   
		}
	}
	
	
	private Node findSuccessor(Node delNode){  
		Node parent = delNode;  
		Node successor = delNode;  
		Node current = delNode.getRightNode();  
        while(current != null){  
            parent = successor;  
            successor = current;  
            current = current.getLeftNode();  
        }  
        if(successor != delNode.getRightNode()){  
            parent.setLeftNode(successor.getRightNode());
            successor.setRightNode(delNode.getRightNode());  
        }  
        return successor;  
    }  

	@Test
	public void test() {
		Tree tree = new Tree();
		tree.insert(30);
		tree.insert(9);
		tree.insert(94);
		tree.insert(5);
		tree.insert(24);
		tree.insert(53);
		tree.insert(98);
		tree.insert(0);
		tree.insert(8);
		tree.insert(21);
		tree.insert(26);
		tree.insert(32);
		tree.insert(61);
		tree.insert(1);
		tree.insert(6);
		tree.insert(17);
		tree.insert(23);
		tree.insert(33);
		tree.insert(55);
		tree.insert(88);

		System.out.println(tree.find(32));
		tree.treeLDR();
		System.out.println("----------最小值----------");
		System.out.println(tree.findMin());
		System.out.println("----------最大值----------");
		System.out.println(tree.findMax());

		tree.delete(9);
		tree.treeLDR();
	}

}
